{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Masseuse LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: massage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按摩师"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对原题稍作改动</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> [1,2,3,1]\n",
    "<strong>输出：</strong> 4\n",
    "<strong>解释：</strong> 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> [2,7,9,3,1]\n",
    "<strong>输出：</strong> 12\n",
    "<strong>解释：</strong> 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> [2,1,4,5,3,1,1,3]\n",
    "<strong>输出：</strong> 12\n",
    "<strong>解释：</strong> 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-masseuse-lcci](https://leetcode.cn/problems/the-masseuse-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-masseuse-lcci](https://leetcode.cn/problems/the-masseuse-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]', '[2,7,9,3,1]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "      if len(nums) == 0:\n",
    "        return 0\n",
    "      if len(nums) == 1:\n",
    "        return nums[0]\n",
    "      dp = [nums[0], max(nums[0:2])]\n",
    "      # 这道题和爬楼梯一样！！！！\n",
    "      # dp[i] = max(dp[i - 1], dp[i - 2] + num[i])\n",
    "      for i in range(2, len(nums)):\n",
    "        dp_i = max(dp[0] + nums[i], dp[1])\n",
    "        dp[0], dp[1] = dp[1], dp_i\n",
    "      return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f0 = 0\n",
    "        f1 = 0\n",
    "        for i in range(n):\n",
    "            tmp = max(f1, (f0+nums[i]))\n",
    "            f0 = f1\n",
    "            f1 = tmp\n",
    "        return f1\n",
    "\n",
    "\n",
    "\n",
    "        # f = [0] * (n+2)\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     f[i+2] = max(f[i+1], (f[i]+nums[i]))\n",
    "        # return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        if len(nums)<3:\n",
    "            return max(nums)\n",
    "        l1=nums[0]\n",
    "        l2=max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            l1,l2=l2,max(l1+nums[i],l2)\n",
    "        return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        if n == 2:\n",
    "            return max(nums)\n",
    "\n",
    "\n",
    "        dp = [0] * (n)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[1],dp[0])\n",
    "\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(nums[i]+ dp[i-2], dp[i-1])\n",
    "        \n",
    "        return dp[n-1]\n",
    "        \n",
    "        #dp[i] = max(接nums[i] + dp[i-2], 不接dp[i-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        dp[1] = nums[0]\n",
    "        for i in range(2, len(dp)):\n",
    "            dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp0, dp1 = 0, nums[0]\n",
    "        for i in range(1, n):\n",
    "            tdp0 = max(dp0, dp1)   # 计算 dp[i][0]\n",
    "            tdp1 = dp0 + nums[i]   # 计算 dp[i][1]\n",
    "            dp0, dp1 = tdp0, tdp1\n",
    "        \n",
    "        return max(dp0, dp1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: list[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.insert(0, -1)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return nums[1]\n",
    "        elif n == 2:\n",
    "            return max(nums[1], nums[2])\n",
    "        elif n == 3:\n",
    "            return max(nums[1] + nums[3], nums[2])\n",
    "        a = nums[1]\n",
    "        b = max(nums[1], nums[2])\n",
    "        c = max(nums[1] + nums[3], nums[2])\n",
    "        for i in range(4, n + 1):\n",
    "            a,b,c = b,c,max((max(a, b) + nums[i]), (max(b, c)))\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return nums[0] if nums else 0\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0], dp[1] = nums[0], max(nums[1], nums[0])\n",
    "        for i in range(2, len(nums)):\n",
    "            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = last1 = last2 = maxdp = 0\n",
    "        for i in range(n):\n",
    "            dp = max(last1, nums[i] + last2)\n",
    "            maxdp = max(maxdp, dp)\n",
    "            last2 = last1\n",
    "            last1 = dp\n",
    "        return maxdp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp_zero = [0] * n\n",
    "        dp_one = [0] * n\n",
    "        print(dp_zero)\n",
    "        print(dp_one)\n",
    "        dp_one[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp_zero[i] = max(dp_zero[i-1],dp_one[i-1])\n",
    "            dp_one[i] = dp_zero[i-1] + nums[i]\n",
    "        return max(dp_one[-1],dp_zero[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        dp = [[0,0] for i in range(n)]\n",
    "        dp[0][1] = nums[0] #拿当前值\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i][1] = max(dp[i-1][0] + nums[i],dp[i-1][1])\n",
    "            dp[i][0] = max(dp[i-1][1],dp[i-1][0])\n",
    "            \n",
    "        return max(dp[n-1][0],dp[n-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[]\n",
    "[1,2,3,1]\n",
    "[2,7,9,3,1]\n",
    "[2,1,4,5,3,1,1,3]\n",
    "\n",
    "Array, Dynamic Programming\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "        if n == 1: return nums[0]\n",
    "        if n == 2: return max(nums)\n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = nums[0]\n",
    "        dp[2] = nums[1]\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(dp[0], nums[1])\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i-2]+nums[i], dp[i-1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n+2)\n",
    "        ans = 0\n",
    "        for i in range(2,n+2):\n",
    "            dp[i] = max(dp[i-1],dp[i-2] + nums[i-2])\n",
    "            ans = max(ans,dp[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        dp = [0] * 2\n",
    "        for num in nums:\n",
    "            dp[0], dp[1] = max(dp), dp[0] + num\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 1:\n",
    "            return 0\n",
    "        a = 0\n",
    "        b = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            a, b = max(a, b), a + nums[i]\n",
    "        return max(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def massage(self, nums: List[int]) -> int:\n",
    "#         length = len(nums)\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "\n",
    "#         if length == 1:\n",
    "#             return nums[0]\n",
    "#         else:\n",
    "#             prev = nums[0]\n",
    "#             cur = max(prev, nums[1])\n",
    "#             for i in range(2, length):\n",
    "#                 cur, prev = max(prev + nums[i], cur), cur\n",
    "#             return cur\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        dp = [0 for _ in range(n+2)] \n",
    "        for i in range(2,n+2):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i-2])\n",
    "            res = max(dp[i],res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        # if len(nums) == 0:\n",
    "        #     return 0\n",
    "        # if len(nums) == 1:\n",
    "        #     return nums[0]\n",
    "        # dp = [0] * len(nums)\n",
    "        # dp[0] = nums[0]\n",
    "        # dp[1] = max(nums[0], nums[1])\n",
    "        # for i in range(2, len(nums)):\n",
    "        #     dp[i] = max(dp[i-1], dp[i-2] + nums[i])\n",
    "            \n",
    "        # return max(dp[len(nums)-2], dp[len(nums) - 1])\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        not_choice = 0\n",
    "        choice = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            not_choice, choice = max(not_choice, choice), not_choice + nums[i]\n",
    "\n",
    "        return max(not_choice, choice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0,nums[0]]\n",
    "        for i in range(1,n):\n",
    "            dp = [max(dp), nums[i]+dp[0]]\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        # dp[i][0] 表示i天休息了 \n",
    "        # dp[i][1] 表示i天在工作\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        dp = [[0,0] for i in range(len(nums))]\n",
    "        dp[0][1] = nums[0]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            \n",
    "            dp[i][0] = max(dp[i-1][0],dp[i-1][1])\n",
    "            dp[i][1] = dp[i-1][0]+nums[i]\n",
    "\n",
    "        return max(dp[-1])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        dp0 = 0\n",
    "        dp1 = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            tmp = dp1\n",
    "            dp1 = max(dp1, dp0 + nums[i])\n",
    "            dp0 = tmp\n",
    "        return dp1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums)<=2:\n",
    "            return max(nums)\n",
    "        nums[2]+=nums[0]\n",
    "        for i in range(3,len(nums)):\n",
    "            nums[i]+=max(nums[i-2],nums[i-3])\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        nmax1 = nmax2 = 0\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            nmax1 , nmax2 = max(nmax1,nmax2+nums[i]) , nmax1\n",
    "            i +=1\n",
    "        return max(nmax1 , nmax2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return max(nums) if nums else 0\n",
    "        dp = [nums[0]]*len(nums)\n",
    "        dp[1] = max(nums[:2])\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        dp = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums)):\n",
    "            dp[i+1] = max(dp[i], dp[i-1]+nums[i])\n",
    "        return dp[len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef massage(self, nums: List[int]) -> int:\n",
    "\t\tif not nums:\n",
    "\t\t\treturn 0\n",
    "\t\tif len(nums) == 1:\n",
    "\t\t\treturn nums[0]\n",
    "\t\tans = [nums[0], nums[1]] + [0 for _ in range(len(nums) - 2)]\n",
    "\t\tfor i in range(2, len(nums)):\n",
    "\t\t\tans[i] = max(ans[:i - 1]) + nums[i]\n",
    "\t\treturn max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if(nums==[]):\n",
    "            return 0\n",
    "        elif(len(nums)==1):\n",
    "            return nums[0]\n",
    "        elif(len(nums)==2):\n",
    "            return max(nums[0],nums[1])\n",
    "        nums[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            nums[i] = max(nums[i]+nums[i-2],nums[i-1])\n",
    "        return nums[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) < 3:\n",
    "            return max(nums)\n",
    "\n",
    "        dp1 = nums[0]\n",
    "        dp2 = max(nums[:2])\n",
    "        for i in range(2, len(nums)):\n",
    "            dp = max(dp1+nums[i], dp2)\n",
    "            dp1 = dp2\n",
    "            dp2 = dp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] =nums[0]\n",
    "        if n>=2:\n",
    "            dp[1] = max(nums[0],nums[1])\n",
    "            for i in range(2,n):\n",
    "                dp[i] = max(dp[i-2]+nums[i],dp[i-1])\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        dp0, dp1 = 0, nums[0]\n",
    "        for i in range(1, n):\n",
    "            tdp0 = max(dp0, dp1)\n",
    "            tdp1 = dp0 + nums[i]\n",
    "            dp0, dp1 = tdp0, tdp1\n",
    "        return max(dp0, dp1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        # 只需要最优值,不需要最优解, 适合动规\n",
    "        # 1.定义状态\n",
    "        # dp[i]表示当前最大的预约时长,但是因为对于今天来说有两种状态,接收预约和不接受预约\n",
    "        # 所以增加一个维度,\n",
    "        # dp[i][0] 表示今天不接受预约的当前的最大时长. dp[i][1]表示今天接受预约的最大时长\n",
    "        # 2. 状态转移方程\n",
    "        #  dp[i][0] = max(dp[i-1][1], dp[i-1][0])  # 今天不接受预约:要么昨天没接受预约，要么昨天接受了预约(每天都是两种状态)\n",
    "        #  dp[i][1]= dp[i-1][0] + nums[i]  # 今天接受了预约: 昨天没接收预约转移来的,再加上今天的状态\n",
    "        # 3. 临界值\n",
    "        # dp[0][0]=0  dp[0][1] = nums[0]\n",
    "\n",
    "        Len = len(nums)\n",
    "        if Len == 0:\n",
    "            return 0\n",
    "        elif Len == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [[0] * 2 for _ in range(Len)] # 初始化二维数组\n",
    "        print(dp)\n",
    "        dp[0][0]=0\n",
    "        dp[0][1] = nums[0]\n",
    "\n",
    "        for i in range(1, Len):\n",
    "            dp[i][0] = max(dp[i-1][1], dp[i-1][0])\n",
    "            dp[i][1]= dp[i-1][0] + nums[i]\n",
    "\n",
    "        return max(dp[Len-1][1], dp[Len-1][0])  # 最后输出二维DP数组的最后一天的最大值\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp0, dp1 = 0, nums[0]\n",
    "        for i in range(1, n):\n",
    "            tdp0 = max(dp0, dp1)\n",
    "            tdp1 = dp0 + nums[i]\n",
    "            dp0, dp1 = tdp0, tdp1\n",
    "        return max(dp0, dp1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        # 边界问题\n",
    "        # 如果只有一个\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        # 如果只有两个呢？\n",
    "        if len(nums) == 2:\n",
    "            result = max(nums[0], nums[1])\n",
    "            return result\n",
    "\n",
    "        # 三个及以上\n",
    "        cur = 0 # 当前的结果\n",
    "        prev = 0 # 上一个的结果\n",
    "        \n",
    "        for num in nums:\n",
    "            cur, prev = max(cur, prev + num), cur\n",
    "            \n",
    "        return max(cur, prev)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        n = len(nums)\n",
    "        re1,re2 = 0,nums[0]\n",
    "        for i in range(1,n):\n",
    "            tmp1 = max(re1,re2)\n",
    "            tmp2 = re1+nums[i]\n",
    "            re1,re2 = tmp1,tmp2\n",
    "        return max(re1,re2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        num=len(nums)\n",
    "        dp=[0]*2+[0]*num\n",
    "        for i in range(num):\n",
    "            dp[i+1]=max(dp[i],dp[i-1]+nums[i])\n",
    "        return max(dp[-1],dp[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * len(nums)\n",
    "        dp0 = nums[0] \n",
    "        dp1 = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            dp = max(dp1, dp0+nums[i])\n",
    "            dp0 = dp1 \n",
    "            dp1 = dp\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "        dp = [(0,0)] * n\n",
    "        dp[0] = (0,nums[0])\n",
    "        for i in range(1,n):\n",
    "            dp[i] = (max(dp[i-1]),dp[i-1][0]+nums[i])\n",
    "        return max(dp[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef massage(self, nums: List[int]) -> int:\n",
    "\t\tn = len(nums)\n",
    "\t\tif n == 0:\n",
    "\t\t\treturn 0\n",
    "\t\telif n == 1:\n",
    "\t\t\treturn nums[0]\n",
    "\t\telse:\n",
    "\t\t\tnum = n * [0]\n",
    "\t\t\tnum[0] = nums[0]\n",
    "\t\t\tnum[1] = max(nums[0], nums[1])\n",
    "\n",
    "\t\t\tfor i in range(2, n):\n",
    "\t\t\t\tnum[i] = max(num[i - 1], num[i - 2] + nums[i])\n",
    "\n",
    "\t\t\treturn num[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            num = n * [0]\n",
    "            for i in range(0,n):\n",
    "                num[i] = max(num[i-1] , num[i-2] + nums[i])\n",
    "        \n",
    "        return num[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        a,b = 0,nums[0]\n",
    "        for x in nums[1:]:\n",
    "            a,b = b,max(b,a+x)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        # dp[i]表示遍历到i最长总预约时间\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        dp=[0]*(len(nums)+1)\n",
    "        dp[0]=0\n",
    "        dp[1]=nums[0]\n",
    "        for i in range(2,len(nums)+1):\n",
    "            dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        dp = [0] * n\n",
    "        dp [0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef massage(self, nums: List[int]) -> int:\n",
    "\t\tif len(nums) == 0:\n",
    "\t\t\treturn 0\n",
    "\t\telif len(nums) == 1:\n",
    "\t\t\treturn nums[0]\n",
    "\n",
    "\t\tnum = len(nums) * [0]\n",
    "\t\tnum[0],num[1] = nums[0], max(nums[0], nums[1])\n",
    "\n",
    "\t\tfor i in range(2, len(nums)):\n",
    "\t\t\tnum[i] = max(num[i - 1], num[i - 2] + nums[i])\n",
    "\n",
    "\t\treturn num[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2] + nums[i])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        dp0, dp1 = 0, nums[0]\n",
    "        for i in range(1, n):\n",
    "            tdp0 = max(dp0, dp1)   # 计算 dp[i][0]\n",
    "            tdp1 = dp0 + nums[i]   # 计算 dp[i][1]\n",
    "            dp0, dp1 = tdp0, tdp1\n",
    "        \n",
    "        return max(dp0, dp1)\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/the-masseuse-lcci/solutions/166465/an-mo-shi-by-leetcode-solution/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        if l==0:return 0\n",
    "        if l<=2:return max(nums)\n",
    "        m=[0]*l\n",
    "        m[0]=nums[0]\n",
    "        m[1]=nums[1]\n",
    "        ma=m[0]\n",
    "        for i in range(2,l):\n",
    "            m[i]=ma+nums[i]\n",
    "            if m[i-1]>ma:ma=m[i-1]\n",
    "        return max(m[-1],m[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        elif len(nums) == 0:\n",
    "            return 0\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0],dp[1] = nums[0],max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp0 = nums[0] \n",
    "        dp1 = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            dp = max(dp1, dp0+nums[i])\n",
    "            dp0 = dp1 \n",
    "            dp1 = dp\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp0 = nums[0] \n",
    "        dp1 = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            dp = max(dp1, dp0+nums[i])\n",
    "            dp0 = dp1 \n",
    "            dp1 = dp\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * len(nums)\n",
    "        dp0 = nums[0] \n",
    "        dp1 = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            dp = max(dp1, dp0+nums[i])\n",
    "            dp0 = dp1 \n",
    "            dp1 = dp\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        # 打家劫舍换皮青春版\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "        if n == 1: return nums[0]\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])\n",
    "        return dp[n - 1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n<=2:\n",
    "            return max(nums)\n",
    "        dp1,dp0=nums[1],nums[0]\n",
    "        dp2=max(dp0+nums[2],dp1)\n",
    "        for i in range(3,n):\n",
    "            temp=max(dp0+nums[i],dp1+nums[i],dp2)\n",
    "            dp0,dp1,dp2=dp1,dp2,temp\n",
    "        return dp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        if len(nums)==1:return nums[0]\n",
    "        # dp=[[0,0]*len(nums)]\n",
    "        dp=[[0,0]for i in range(len(nums))]\n",
    "        dp[0][0]=0\n",
    "        dp[0][1]=nums[0]\n",
    "        print(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i][1]=dp[i-1][0]+nums[i]\n",
    "            dp[i][0]=max(dp[i-1][1],dp[i-1][0])\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        dp = [0]*n\n",
    "        dp[0]=nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,n):\n",
    "            dp[i]=max(dp[i-1],dp[i-2]+nums[i])#当前不接受和当前接受的最大值\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if(len(nums)==0):\n",
    "            return 0\n",
    "        if(len(nums)==1):\n",
    "            return nums[0]\n",
    "        if(len(nums)==2):\n",
    "            return max(nums[0],nums[1])\n",
    "        if(len(nums)==3):\n",
    "            return max(nums[0]+nums[2],nums[1])\n",
    "        res=[0 for _ in range(len(nums))]\n",
    "        res[0]=nums[0]\n",
    "        res[1]=max(nums[0],nums[1])\n",
    "        res[2]=max(nums[0]+nums[2],nums[1])\n",
    "        for i in range(3,len(nums)):\n",
    "            res[i]=max(res[i-2],res[i-3])+nums[i]\n",
    "        print(res)\n",
    "        return max(res[-1],res[-2])       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "        \n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef massage(self, nums: List[int]) -> int:\n",
    "\t\tn = len(nums)\n",
    "\t\tif n == 0:\n",
    "\t\t\treturn 0\n",
    "\t\telif n == 1:\n",
    "\t\t\treturn nums[0]\n",
    "\t\telse:\n",
    "\t\t\tnum = n * [0]\n",
    "\t\t\tnum[0] = nums[0]\n",
    "\t\t\tnum[1] = max(nums[0], nums[1])\n",
    "\n",
    "\t\t\tfor i in range(2, n):\n",
    "\t\t\t\tnum[i] = max(num[i - 1], num[i - 2] + nums[i])\n",
    "\n",
    "\t\t\treturn num[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        sz = len(nums)\n",
    "        if sz == 0:\n",
    "            return 0\n",
    "        if sz == 1:\n",
    "            return nums[0]\n",
    "        if sz == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp = [0] * sz\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, sz):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return dp[sz-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            num = n * [0]\n",
    "            num[0] = nums[0]\n",
    "            num[1] = max(nums[0],nums[1])\n",
    "            for i in range(2,n):\n",
    "                num[i] = max(num[i-1] , num[i-2] + nums[i])\n",
    "        \n",
    "        return num[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        n = len(nums)\n",
    "        if n<3:return max(nums)\n",
    "        dp = [0]*n\n",
    "        dp[0],dp[1],dp[2] = nums[0],nums[1],nums[0]+nums[2]\n",
    "        for i in range(3,n):\n",
    "            dp[i] = max(dp[i-3],dp[i-2])+nums[i]\n",
    "        return max(dp[-1],dp[-2])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef massage(self, nums: List[int]) -> int:\n",
    "\t\tn = len(nums)\n",
    "\t\tif n == 0:\n",
    "\t\t\treturn 0\n",
    "\t\telif n == 1:\n",
    "\t\t\treturn nums[0]\n",
    "\t\telse:\n",
    "\t\t\tnum = n * [0]\n",
    "\t\t\tnum[0] = nums[0]\n",
    "\t\t\tnum[1] = max(nums[0], nums[1])\n",
    "\n",
    "\t\t\tfor i in range(2, n):\n",
    "\t\t\t\tnum[i] = max(num[i - 1], num[i - 2] + nums[i])\n",
    "\n",
    "\t\t\treturn num[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        n = len(nums)\n",
    "        if n<3:return max(nums)\n",
    "        dp = [0]*n\n",
    "        dp[0],dp[1],dp[2] = nums[0],nums[1],nums[0]+nums[2]\n",
    "        for i in range(3,n):\n",
    "            dp[i] = max(dp[i-3],dp[i-2])+nums[i]\n",
    "        return max(dp[-1],dp[-2])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0 \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp0 = nums[0] \n",
    "        dp1 = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            dp = max(dp1, dp0+nums[i])\n",
    "            dp0 = dp1 \n",
    "            dp1 = dp\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        k=len(nums)\n",
    "        if k==0:\n",
    "            return 0\n",
    "        elif k==1:\n",
    "            return nums[0]\n",
    "        elif k==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        else:\n",
    "            dp=[0]*k\n",
    "            dp[0]=nums[0]\n",
    "            dp[1]=nums[1]\n",
    "            dp[2]=nums[0]+nums[2]\n",
    "            for i in range(3,k):\n",
    "                dp[i]=max((dp[i-2]+nums[i]),(dp[i-3]+nums[i]))\n",
    "            return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def massage(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        n = len(nums)\n",
    "        if n<3:return max(nums)\n",
    "        dp = [0]*n\n",
    "        dp[0],dp[1],dp[2] = nums[0],nums[1],nums[0]+nums[2]\n",
    "        for i in range(3,n):\n",
    "            dp[i] = max(dp[i-3],dp[i-2])+nums[i]\n",
    "        return max(dp[-1],dp[-2])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
